<!DOCTYPE html>
<html>

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <title>标题</title>
</head>

<body>
    <script>
        /* 
            1.核心思路：
                设置一个增量，依据增量将数组分成若干子序列，子序列之间进行插入排序
                比如/2求增量最常用，长度为11的数组，11/2增量是5，0 5 10是第一组进行插入排序；1 6是第二组进行插入排序
            2.时间复杂度
                最差O(n ^ 2) 增量就是1
                最好O(n) 本身就是有序
                平均O(n ^ 1.3)
                空间复杂度O(1)
            3.是原地排序
            4.不是稳定排序 有可能影响相同元素前后的相对位置
                没有说哪个增量一定是好的
                HIbbard增量：1,3，7，15 => O(n ^ 3/2)
                Sedgewick增量：1,5,19 => O(n ^ 4/3) 
        */
        function shellSort(nums) {
            // 设置初始基准值
            let gap = Math.floor(nums.length / 2)
            // 开始进行while循环
            while (gap > 0) {
                let j = gap
                while (j >= gap && j < nums.length) {
                    if (nums[j] < nums[j - gap]) {
                        // 交换元素，交换之后j-gap和j之间是相对有序的
                        let temp = nums[j - gap]
                        nums[j - gap] = nums[j]
                        nums[j] = temp
                    }
                    j++
                }
                gap = Math.floor(gap / 2) // 更新下一波的基准值
            }
            return nums
        }
        // console.log(shellSort([5, 3, 9, 12, 6, 1, 7, 2, 4, 11, 8, 10]));
        console.log(shellSort([5, 8, 6, 3, 9, 2, 1, 7]));
    </script>

</body>

</html>